import json
import time
from typing import List

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        # 分而治之
        # 递归基：a^0 = 1
        if not b: 
            return 1
        # 递归：a^[b1,b2,...bn] = a^[b1,b2,...b_(n-1)]^10 * a^bn
        return (self.superPow(a, b[:-1]) % 1337) ** 10 * (a % 1337) ** b[-1] % 1337

class OptimizedSolution:
    """优化版本的解法，用于对比"""
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        
        def pow_mod(base, exp, mod):
            """快速幂取模"""
            if exp == 0:
                return 1
            result = 1
            base = base % mod
            while exp > 0:
                if exp % 2 == 1:
                    result = (result * base) % mod
                exp = exp >> 1
                base = (base * base) % mod
            return result
        
        def super_pow_helper(a, b):
            if not b:
                return 1
            
            last_digit = b[-1]
            remaining = b[:-1]
            
            # a^[1,2,3,4] = (a^[1,2,3])^10 * a^4
            part1 = pow_mod(super_pow_helper(a, remaining), 10, MOD)
            part2 = pow_mod(a, last_digit, MOD)
            
            return (part1 * part2) % MOD
        
        return super_pow_helper(a, b)

class IterativeSolution:
    """迭代版本的解法"""
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        
        def pow_mod(base, exp, mod):
            result = 1
            base = base % mod
            while exp > 0:
                if exp % 2 == 1:
                    result = (result * base) % mod
                exp = exp >> 1
                base = (base * base) % mod
            return result
        
        result = 1
        a = a % MOD
        
        for digit in b:
            result = pow_mod(result, 10, MOD)
            result = (result * pow_mod(a, digit, MOD)) % MOD
        
        return result

def load_test_cases(filename="super_pow_test_cases.json"):
    """加载测试用例"""
    try:
        with open(filename, 'r', encoding='utf-8') as f:
            data = json.load(f)
        return data["test_cases"], data.get("statistics", {})
    except FileNotFoundError:
        print(f"测试文件 {filename} 不存在，请先运行 gen.py")
        return [], {}

def run_single_test(solution, test_case, test_id):
    """运行单个测试用例"""
    a = test_case["input_a"]
    b = test_case["input_b"]
    expected = test_case["expected"]
    description = test_case["description"]
    
    try:
        start_time = time.time()
        result = solution.superPow(a, b)
        end_time = time.time()
        
        is_correct = result == expected
        
        return {
            "test_id": test_id,
            "description": description,
            "input_a": a,
            "input_b": b,
            "expected": expected,
            "actual": result,
            "is_correct": is_correct,
            "execution_time": end_time - start_time,
            "status": "PASS" if is_correct else "FAIL"
        }
    except Exception as e:
        return {
            "test_id": test_id,
            "description": description,
            "input_a": a,
            "input_b": b,
            "expected": expected,
            "actual": None,
            "is_correct": False,
            "execution_time": 0,
            "status": "ERROR",
            "error": str(e)
        }

def run_comprehensive_test():
    """运行全面测试"""
    test_cases, stats = load_test_cases()
    if not test_cases:
        return
    
    solution = Solution()
    
    print("=== 超级幂算法测试 ===")
    print(f"总测试用例数: {len(test_cases)}")
    print(f"模数: {stats.get('modulus', 1337)}")
    print()
    
    passed = 0
    failed = 0
    errors = 0
    total_time = 0
    
    print("测试结果详情:")
    print("-" * 90)
    
    for i, test_case in enumerate(test_cases):
        result = run_single_test
